package com.leetcode;


import java.util.Arrays;

/**
 * 1187. 使数组严格递增 (困难)
 * 给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。
 * 每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2
 * .length，然后进行赋值运算 arr1[i] = arr2[j]。
 * 如果无法让 arr1 严格递增，请返回 -1。
 */
public class LeetCode1187 {

    public static void main(String[] arg0) {
        int[] data1 = new int[]{1,5,3,6,7};
        int[] data2 = new int[]{1,3,2,4};
        System.out.println("使 data1 数组严格递增的最小替换次数 = " + makeArrayIncreasing(data1, data2));
    }

    // 结果只需要让arr1严格递增
    public static int makeArrayIncreasing(int[] arr1, int[] arr2) {
        if (arr1.length == 1) return 0;

        // 对 arr2 排序去重，严格递增不会有相同数字的存在
        arr2 = Arrays.stream(arr2).sorted().distinct().toArray();
        
        // 最大替换次数就是短数组的长度
        int maxRes = Math.min(arr1.length, arr2.length);

        // 构建动态规划dp数组，这里采用二维数组，行代表 arr1 的长度，列代表替换次数，值代表替换次数后递增数列最后那位的值
        int[][] dp = new int[arr1.length + 1][maxRes + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = -1; // 动态规划数组所有位置填充int最大值后将第一位置为-1
        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 0; j <= Math.min(i, arr2.length); j++) {
                if (arr1[i - 1] > dp[i - 1][j]) {
                    dp[i][j] = arr1[i - 1];
                }

                if (j > 0 && dp[i - 1][j - 1] != Integer.MAX_VALUE) {
                    /* 查找严格大于 dp[i - 1][j - 1] 的最小元素 */
                    int idx = binarySearch(arr2, j - 1, dp[i - 1][j - 1]);
                    if (idx < arr2.length) {
                        dp[i][j] = Math.min(dp[i][j], arr2[idx]);
                    }
                }

                // 结果一定在数组最后一行中，如果最后一行都没赋值，还是int最大值，就是无法严格递增
                // 而最先赋值的就是最小次数，因为 j 是从0递增的，返回的结果也可能是0
                if (i == arr1.length && dp[i][j] != Integer.MAX_VALUE) {
                    for (int k = 0; k < dp.length; k++) {
                        System.out.println(Arrays.toString(dp[k]));
                    }
                    return j;
                }
            }
        }

        return -1;
    }

    // 二分查找刚好大于target的数的下标，返回的low可能数组越界
    public static int binarySearch(int[] arr, int low, int target) {
        int high = arr.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

}
